package 排序.插入排序;

public class Shell_sort {
    /**
     * 希尔排序
     * 时间复杂度：O(n^1.3~n^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */
    public static void ShellSort(int[] array){
        //跳跃式分组    先预排序 + 排序.插入排序(gap=1)
        int gap= array.length;
        while(gap>1){
            gap=gap/3+1;
            shell(array,gap);
        }
    }

    public static void shell(int[] array,int gap){
        int j;

        for(int i=gap;i<array.length;i++){
            int temp=array[i];
            j=i-gap;

            while(j>=0&&array[j]>temp){
                array[j+gap]=array[j];
                j-=gap;
            }
            array[j+gap]=temp;
        }
    }
}
